package ms.sudoku.util;

import java.util.Arrays;
import java.util.Iterator;

public class IntSet implements Cloneable, Iterable<Integer> {
	public static final int MAX_CAPACITY = 32;
	private int bits;
	private int capacity;
	private int size;

	public IntSet() {
		this(MAX_CAPACITY);
	}

	public IntSet(int capacity) {
		this(capacity, false);
	}

	public IntSet(int capacity, boolean addAll) {
		this.capacity = capacity;
		if (addAll) {
			this.addAll();
		} else {
			this.clear();
		}
	}

	public boolean contains(int number) {
		return (bits & (1 << number)) != 0;
	}

	/**
	 * Determines whether all of the specified numbers are set in the bit array.
	 * 
	 * @param numbers
	 *            The numbers.
	 * @return Whether all of the specified numbers in the bit array are set.
	 */
	public boolean containsAll(int[] numbers) {
		for (int n : numbers) {
			if (!this.contains(n)) {
				return false;
			}
		}
		return true;
	}

	/**
	 * Determines whether any of the specified numbers are set in the bit array.
	 * 
	 * @param numbers
	 *            The numbers.
	 * @return Whether any of the specified numbers in the bit array are set.
	 */
	public boolean containsAny(int[] numbers) {
		for (int n : numbers) {
			if (this.contains(n)) {
				return true;
			}
		}
		return false;
	}

	public boolean add(int num) {
		boolean contains = this.contains(num);
		if (!contains) {
			bits |= (1 << num);
			size++;
		}
		return !contains;
	}

	public boolean remove(int num) {
		boolean contains = this.contains(num);
		if (contains) {
			size--;
			bits &= ~(1 << num);
		}
		return contains;
	}

	public void addAll() {
		bits = 0xFFFFFFFF;
		size = capacity;
	}

	public int pop() {
		int num = 0;
		for (; 0 == (this.bits & (1 << num)); num++)
			;
		this.remove(num);
		return num;
	}

	public void clear() {
		bits = 0;
		size = 0;
	}

	public int capacity() {
		return capacity;
	}

	public int size() {
		return size;
	}

	public boolean isEmpty() {
		return 0 == size();
	}

	public Iterator<Integer> iterator() {
		return new Iterator<Integer>() {
			private int pos = 0;
			private boolean holding = false;
			private boolean hasNext = false;

			@Override
			public boolean hasNext() {
				if (false == holding) {
					this.findNext();
				}
				return hasNext;
			}

			@Override
			public Integer next() {
				if (false == holding) {
					this.findNext();
				}
				this.holding = false;
				return pos++;
			}

			void findNext() {
				if (true == holding) {
					return;
				}
				while (true) {
					if (pos >= capacity) {
						holding = true;
						hasNext = false;
						return;
					}
					if (0 != (bits & (1 << pos))) {
						holding = true;
						hasNext = true;
						return;
					} else {
						pos++;
					}
				}
			}

			@Override
			public void remove() {
				throw new UnsupportedOperationException("not implememts yet");
			}
		};
	}

	public int[] toArray() {
		int[] values = new int[this.size()];
		int pos = 0;
		for (int i = 0; i < this.capacity(); i++) {
			if (this.contains(i))
				values[pos++] = i;

		}
		return values;
	}

	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + bits;
		result = prime * result + size;
		return result;
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		IntSet other = (IntSet) obj;
		if (bits != other.bits)
			return false;
		if (size != other.size)
			return false;
		return true;
	}

	@Override
	public IntSet clone() {
		try {
			return (IntSet) super.clone();
		} catch (CloneNotSupportedException e) {
			// should not happen
			IntSet c = new IntSet();
			c.bits = this.bits;
			c.capacity = this.capacity;
			c.size = this.size;
			return c;
		}
	}

	public String toString() {
		return Arrays.toString(this.toArray());
	}

	public static void main(String[] args) {
		IntSet set = new IntSet();
		set.add(2);
		set.add(4);
		set.add(5);
		set.add(7);
		set.add(31);
		for (Iterator<Integer> iter = set.iterator(); iter.hasNext();) {
			System.err.println(iter.next());
		}
		while (false == set.isEmpty()) {
			System.out.println(set.pop() + " removed: " + set);
		}
	}
}
